package com.ojtest.demo;

class code3 {
    public String longestPalindrome(String s) {
        char[] chs = s.toCharArray();
        int n = chs.length, maxLen = 1;
        int left = 0, right = 0;
        boolean[][] dp = new boolean[n][n];
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if (chs[i] == chs[j]) {
                    dp[i][j] = (i == j) || (i + 1 == j) ? true : dp[i + 1][j - 1];
                }
                if (dp[i][j] && (j - i + 1 > maxLen)) {
                    maxLen = j - i + 1;
                    left = i;
                    right = j;
                }
            }
        }
        return s.substring(left, right + 1);
    }
}
